home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C/C++ Users Group Library 1996 July
/
C-C++ Users Group Library July 1996.iso
/
vol_100
/
155_01
/
btree1.c
< prev
next >
Wrap
C/C++ Source or Header
|
1990-10-07
|
16KB
|
436 lines
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include "btree.h"
/* Author: Ray Swartz
* Berkeley Decision/Systems, Inc.
* P.O. Box 2528
* Santa Cruz, Calif. 95063
* Last Modified: 4/28/85
*
* ANY USE OF THESE LIBRARY ROUTINES EITHER PERSONAL OR COMMERCIAL
* IS ALLOWED UPON THE CONDITION THAT THE USER IDENTIFY THEM
* AS BEING USED IN THE PROGRAM. IDENTIFYING INFORMATION MUST
* APPEAR IN THE PROGRAM DOCUMENTATION OR ON THE TERMINAL SCREEN.
*
* #################################
* # UNATTRIBUTED USE IS FORBIDDEN #
* #################################
*
* The insert routine was directly translated from the algorithm
* in D. Knuth's Volume 3 of The Art of Computer Programming
* (Sorting and Searching) pages 455 - 457. Single letter
* variables (p, q, r, s) are used to make the algorithm steps
* more obvious.
*/
/*
* Modifier: Honma Michimasa
*/
/**** Function prot. ********/
int insert(char *argkey, long recnbr, struct keyinfo *fileinfo);
/* insert key (argkey) into tree */
void link(int alpha1, struct node *node1, int alpha2, struct node *node2);
void nbr_link(long *nbr, int alpha, struct node *node1);
/* set a record number according to alpha */
void link_nbr(int alpha, struct node *node1, long nbr);
/* set a link according to alpha */
void node_bal(int alpha, struct node *node1, struct node *node2, struct node *node3);
/* node balancing in Step A9 */
void delete_key(long node_nbr, struct node *current_node, struct keyinfo *fileinfo);
int get_next(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
/* retrieve next higher node */
int find_key(char *key1, long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
/* locate a key */
int insert(char *argkey, long recnbr, struct keyinfo *fileinfo) /* insert key (argkey) into tree */
/* struct keyinfo *fileinfo; file to insert key into */
/* char *argkey; key to insert */
/* long recnbr; record number of corresponding data record */
{
static long top; /* where balancing will have to take place, if at all */
static long p_rec;
static long s_rec;
static long q_rec;
static long r_rec;
static struct node q_node, s_node, r_node, p_node;
static int alloc_flag = NO; /* flag for pointer space allocation */
int compare; /* holds key comparison values */
if (fileinfo->next_avail >= MAX_NODES) {
printf("Only %d nodes allowed in a keyfile\n");
exit(1);
}
if(alloc_flag == NO) { /* set up key pointers in node structures */
q_node.key = malloc(fileinfo->keylength + 1); /* first call to */
s_node.key = malloc(fileinfo->keylength + 1); /* insert function */
p_node.key = malloc(fileinfo->keylength + 1);
r_node.key = malloc(fileinfo->keylength + 1);
alloc_flag = YES;
}
if (fileinfo->list_head == 0) { /* no records in list */
fileinfo->list_head = 1; /* insert key as head of list */
p_node.balance = p_node.right_link = p_node.left_link = 0;
p_node.delete_flag = NO;
p_node.rec_nbr = recnbr;
strcpy(p_node.key, argkey);
write_node(1L, &p_node, fileinfo);
fileinfo->next_avail++;
fileinfo->nbr_in_list++;
return(YES);
}
top = TOP; /* initialize to see if list head changes */
p_rec = fileinfo->list_head; /* Step A1 (find spot to insert) */
s_rec = fileinfo->list_head;
while(1) {
get_node(p_rec, &p_node, fileinfo);
if ((compare = strcmp(argkey, p_node.key)) < 0) { /* Step A2 */
q_rec = p_node.left_link; /* Step A3 (move left) */
if (q_rec == END) { /* insert here */
q_rec = fileinfo->next_avail++;
p_node.left_link = q_rec;
break; /* loop exit */
}
else { /* look again from this node */
get_node(q_rec, &q_node, fileinfo);
if (q_node.balance != 0) {
top = p_rec;
s_rec = q_rec;
}
}
p_rec = q_rec;
}
else { /* Step A4 (move right) */
q_rec = p_node.right_link;
if (q_rec == END) { /* insert here */
q_rec = fileinfo->next_avail++;
p_node.right_link = q_rec;
break; /* loop exit */
}
else { /* look again from this node */
get_node(q_rec, &q_node, fileinfo);
if (q_node.balance != 0) {
top = p_rec;
s_rec = q_rec;
}
p_rec = q_rec;
}
}
} /* end of while loop */
/* Step 5 (insert key at q_node) */
q_node.left_link = q_node.right_link = END;
q_node.balance = 0;
q_node.delete_flag = NO;
q_node.rec_nbr = recnbr;
strcpy(q_node.key, argkey);
if (write_node(q_rec, &q_node, fileinfo) == NO)
return(NO); /* write failed */
write_node(p_rec, &p_node, fileinfo);
get_node(s_rec, &s_node, fileinfo); /* Step A6 (adjust balance factors) */
if (strcmp(argkey, s_node.key) < 0)
r_rec = p_rec = s_node.left_link;
else
r_rec = p_rec = s_node.right_link;
while (p_rec != q_rec) {
get_node(p_rec, &p_node, fileinfo);
if(strcmp(argkey, p_node.key) < 0) {
p_node.balance = -1;
write_node(p_rec, &p_node, fileinfo);
p_rec = p_node.left_link;
}
else {
p_node.balance = 1;
write_node(p_rec, &p_node, fileinfo);
p_rec = p_node.right_link;
}
}
compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1; /* Step A7 */
if (s_node.balance == 0) { /* Step A7i */
fileinfo->nbr_in_list++;
s_node.balance = compare;
write_node(s_rec, &s_node, fileinfo);
return(YES);
}
else if(s_node.balance == -compare) { /* Step A7ii */
fileinfo->nbr_in_list++;
s_node.balance = 0;
write_node(s_rec, &s_node, fileinfo);
return(YES);
}
else { /* Step A7iii (tree out of balance) */
fileinfo->nbr_in_list++;
get_node(s_rec, &s_node, fileinfo);
get_node(r_rec, &r_node, fileinfo);
if (r_node.balance == compare) { /* Step A8 (single rotate) */
p_rec = r_rec;
link(compare, &s_node, -compare, &r_node);
link_nbr(-compare, &r_node, s_rec);
s_node.balance = r_node.balance = 0;
}
else { /* Step A9 (double rotate) */
nbr_link(&p_rec, -compare, &r_node);
get_node(p_rec, &p_node, fileinfo);
link(-compare, &r_node, compare, &p_node);
link_nbr(compare, &p_node, r_rec);
link(compare, &s_node, -compare, &p_node);
link_nbr(-compare, &p_node, s_rec);
node_bal(compare, &p_node, &s_node, &r_node);
p_node.balance = 0;
write_node(p_rec, &p_node, fileinfo);
}
if (top == TOP) /* Step A10 */
fileinfo->list_head = p_rec; /* balanced at list head */
else { /* balanced at top of a sub-tree */
get_node(top, &q_node, fileinfo);
if (s_rec == q_node.right_link)
q_node.right_link = p_rec;
else
q_node.left_link = p_rec;
write_node(top, &q_node, fileinfo);
}
write_node(s_rec, &s_node, fileinfo);
write_node(r_rec, &r_node, fileinfo);
return(YES);
}
}
void link(int alpha1, struct node *node1, int alpha2, struct node *node2)
/*
int alpha1, alpha2;
struct node *node1, *node2;
*/
{
/* see definition of LINK(a, P) on Knuth pg. 455 (Vol. 3) */
if (alpha1 == -1 && alpha2 == -1)
node1->left_link = node2->left_link;
else if(alpha1 == -1 &&